// 460.[BFS/迷宫足球] maze_football
// https://leetcode.cn/problems/the-maze
// 由空地（用 0 表示）和墙（用 1 表示）组成的迷宫 maze 中有一个球。
// 球可以途经空地向 上、下、左、右 四个方向滚动，且在遇到墙壁前不会停止滚动。
// 当球停下时，可以选择向下一个方向滚动。
// 给你一个大小为 m x n 的迷宫 maze ，以及球的初始位置 start 和目的地
// destination ， 其中 start = [startrow, startcol] 且 destination =
// [destinationrow, destinationcol] 。
// 请你判断球能否在目的地停下：如果可以，返回 true ；否则，返回 false 。
// 你可以 假定迷宫的边缘都是墙壁（参考示例）
// 输入：maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]],
// start = [0,4], destination = [4,4] 输出：true 解释：一种可能的路径是 : 左 ->
// 下 -> 左 -> 下 -> 右 -> 下 -> 右。 输入：maze =
// [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4],
// destination = [3,2] 输出：false
// 解释：不存在能够使球停在目的地的路径。注意，球可以经过目的地，但无法在那里停驻。

#include <bits/stdc++.h>
using namespace std;

#define PF(...) printf(__VA_ARGS__)
#define FRE(x) freopen("d:/oj/" #x ".in", "r", stdin)

// template <typename T,typename U>
// std::pair<T,U> operator+(const std::pair<T,U> & l,const std::pair<T,U> & r) {
//  return {l.first+r.first,l.second+r.second};
//}

class Solution {
  bool hasPath(vector<vector<int>>& maze, vector<int>& start,
               vector<int>& destination) {
    vector<vector<int>> visit(maze.size(), vector<int>(maze[0].size()));
    vector<pair<int, int>> dirs = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
    pair<int, int> posDest = {destination[0], destination[1]};
    queue<pair<int, int>> quePath;
    quePath.push({start[0], start[1]});
    visit[start[0]][start[1]] = 1;
    while (!quePath.empty()) {
      auto cur = quePath.front();
      quePath.pop();
      if (cur == posDest) {
        return true;
      }
      for (auto dir : dirs) {
        int nxtr = cur.first + dir.first;
        int nxtc = cur.second + dir.second;
        while (nxtr >= 0 && nxtc >= 0 && nxtr < maze.size() &&
               nxtc < maze[0].size() && maze[nxtr][nxtc] == 0) {
          nxtr += dir.first;
          nxtc += dir.second;
        }
        nxtr -= dir.first;
        nxtc -= dir.second;
        if (!visit[nxtr][nxtc]) {
          quePath.push({nxtr, nxtc});
          visit[nxtr][nxtc] = 1;
        }
      }
    }
    return false;
  }
};
